UVa/843 - Crypt kicker/843.2.cpp

   1 #include <sstream>
   2 #include <iostream>
   3 #include <map>
   4 #include <string>
   5 #include <vector>
   6 #include <set>
   7
   8 using namespace std;
   9
  10 map<int, set<string> > dict;
  11 map<char, char> solucion;
  12
  13
  14 bool contradice(const string &origen, const string &destino,  map<char, char> crypt){
  15   //cout << "Contradice llamado con " << origen << " y " << destino << endl;
  16
  17   map<char, char> temp;
  18   for (int i=0; i<origen.size(); ++i){
  19     if (temp.count(origen[i]) == 1){
  20       if (temp[origen[i]] != destino[i]){
  21         return true;
  22       }
  23     }else{
  24       for (map<char, char>::iterator j = temp.begin(); j != temp.end(); ++j){
  25         if ((*j).second == destino[i]) return true;
  26       }
  27       temp[origen[i]] = destino[i];
  28     }
  29   }
  30
  31   if (origen.length() != destino.length()) return true;
  32
  33   for (int i=0; i<origen.size(); ++i){
  34     if (crypt.count(origen[i]) == 1){
  35       if (crypt[origen[i]] != destino[i]){
  36         return true;
  37       }
  38     }else{
  39       for (map<char, char>::iterator j = crypt.begin(); j != crypt.end(); ++j){
  40         if ((*j).second == destino[i]) return true;
  41       }
  42     }
  43   }
  44   return false;
  45 }
  46
  47
  48
  49 void asignar(const string &origen, const string &destino, map<char, char> &crypt){
  50   if (origen.size() != destino.size()) return;
  51
  52   for (int i=0; i<origen.size(); ++i){
  53     crypt[origen[i]] = destino[i];
  54   }
  55 }
  56
  57 bool bt(int i, const vector<string> &words, map<char, char> crypt){
  58   if (i >= words.size()){
  59     solucion = crypt;
  60     return true;
  61   }
  62
  63   int len = words[i].length();
  64   set<string> possible = dict[len];
  65
  66   for (set<string>::iterator j = possible.begin(); j != possible.end(); ++j){
  67
  68     /*    if (!contradice(words[i], (*j), crypt)){
  69       map<char, char> copia = crypt;
  70       asignar(words[i], (*j), copia);
  71
  72       if (bt(i+1, words, copia)){
  73         return true;
  74       }
  75
  76     }
  77     */
  78
  79     if (!contradice(words[i], (*j), crypt)){
  80       map<char, char> copia = crypt;
  81       asignar(words[i], (*j), copia);
  82
  83       if (bt(i+1, words, copia)){
  84         return true;
  85       }
  86
  87     }
  88
  89   }
  90   return false;
  91 }
  92
  93 int main(){
  94   int n;
  95   cin >> n;
  96   while (n--){
  97     string s;
  98     cin >> s;
  99     dict[s.length()].insert(s);
 100     //cout << "agregue " << s << " al dict en la posicion " << s.length() << endl;
 101   }
 102   getchar();
 103   string line;
 104   while (getline(cin, line)){
 105     //cout << "Lei esta linea: " << line << endl;
 106
 107     if (line == ""){
 108       cout << "\n";
 109       continue;
 110     }
 111
 112     vector<string> words;
 113     stringstream ss;
 114     ss << line;
 115     string word;
 116     while (ss >> word){
 117       words.push_back(word);
 118
 119       //cout << "Empuje la palabra " << word << " a la lista " << endl;
 120
 121     }
 122     if (bt(0, words, map<char, char>() )){
 123       for (int i=0; i<line.size(); ++i){
 124         if (line[i] == ' ') cout << " ";
 125         else cout << solucion[line[i]];
 126       }
 127       cout << endl;
 128       //cout << "Hay solucion\n";
 129     }else{
 130       for (int i=0; i<line.size(); ++i){
 131         if (line[i] == ' ') cout << " ";
 132         else cout << "*";
 133       }
 134       cout << endl;
 135       //cout << "No hay solucion\n";
 136     }
 137   }
 138 }